package com.gitee.feizns.explore.data_structure.sort;

/**
 * @author feizns
 * @since 2020/1/15
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = new int[100000000];
        for (int i = 0; i < arr.length; i++)
            arr[i] = (int) (Math.random() * arr.length);
//        for (int i = 0; i < arr.length; i++)
//            arr[i] = i;
        TimeWatch t = new TimeWatch();
//        sort(arr);
        MergeSort.mergeSort(arr);
//        InsertSort.insertSort2(arr);
        System.out.println(t.getEnd());
//        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        int h = 1;
        while ( h < (arr.length / 3) ) h = 3 * h + 1;
        while ( h >= 1 ) {
            for (int i = h; i < arr.length; i++) {
                int j = i;
                int val = arr[j];
                for (; j >= h && val < arr[j - h]; j-=h)
                    arr[j] = arr[j - h];
                arr[j] = val;
            }
            h /= 3;
        }
    }

    private static void sort2(int[] arr) {
        int N = arr.length;
        int h = 1;
        while ( h < N / 3 ) h = h * 3 + 1;
        while ( h >= 1 ) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && arr[j] < arr[j - h] ; j-=h) {
                    int tmp = arr[j];
                    arr[j] = arr[j - h];
                    arr[j - h] = tmp;
                }
            }
            h /= 3;
        }
    }

}
